package cn.cxq.learning.math;

import org.junit.jupiter.api.Test;

/**
 * 链接：https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6?toCommentId=9153622
 * 来源：牛客网
 *
 * [编程题]整数中1出现的次数（从1到n整数中1出现的次数）
 * 热度指数：368595时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
 * 算法知识视频讲解
 * 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数
 * 例如，1~13中包含1的数字有1、10、11、12、13因此共出现6次
 *
 * 示例1
 * 输入
 * 13
 * 输出
 * 6
 */
public class NumberOf1Between1AndN {

    @Test
    public void test() {
        System.out.println(NumberOf1Between1AndN_Solution(55));
    }

    // 思路：算出每个位上一出现的次数：
    // （i从0开始）每个位上出现的一的个数= 第i位后的数 × 10的i次方
    //                                      +第i位为1 ? 第i位前的数 : 0
    //                                      +第i位上的数大于1 ? 10的i次方: 0
    // 遍历所有位数求出上述表达式的和即为结果。
    public int NumberOf1Between1AndN_Solution(int n) {
        int temp = n;
        int sum = 0;
        int length = String.valueOf(n).length();

        for (int i = 0; i < length; i++) {
            int pre = (int) (n % Math.pow(10, i)); //第i位前的数
            int last = (int) (n / Math.pow(10, i + 1)); // 第i位后的数
            int cur = temp % 10; //第i位数
            temp /= 10;
            sum += last * Math.pow(10, i) + (cur == 1 ? pre + 1 : 0) + (cur > 1 ? Math.pow(10, i) : 0);
        }

        return sum;
    }
}
